#include <iostream>
#include <stdlib.h>
#include <cmath>
#include <algorithm>
using namespace std;
#define maxn 100
int n,num=1;
typedef struct node 
{
    int col[maxn];
    int top;
}stacktype;
void display(stacktype st)
{
    printf("    第%d个解为:",num++);
    for(int i=1;i<=n;i++)
        printf("(%d,%d) ",i,st.col[i]);
    printf("\n");
}
bool place(stacktype st,int k,int j)
{
    int i=1;
    if(k==1) return true;
    while(i<=k-1)
    {
        if((st.col[i]==j)||(abs(st.col[i]-j)==abs(i-k)))
            return false;
        i++;
    }
    return true;
}
void queen(int n)
{
    int k;
    bool find;
    stacktype st;
    st.top=1;
    st.col[st.top]=0;
    while(st.top!=0)
    {
        k=st.top;
        find=false;
        for(int j=st.col[k]+1;j<=n;j++)
            if(place(st,k,j))
            {
                st.col[k]=j;
                find=true;
                break;
            }
        if(find)
        {
            if(k==n)
            {
                display(st);
            }
            else
            {
                st.top++;
                st.col[st.top]=0;
            }
        }
        else st.top--;
    }
    if(num==1)
        printf("  此%d皇后问题无解!\n",n);
}
int main()
{
    printf("n皇后问题(n<20)求解:n=");
    scanf("%d",&n);
    if(n>20) printf("n必须小于20\n");
    else
    {
        printf(" %d皇后问题的求解情况如下:\n",n);
        queen(n);
    }
    return 0;
}